算法练习4

您所在的位置：网站首页 › 岛屿数量 leetcode › 算法练习4

算法练习4

2023-06-19 10:13| 来源: 网络整理| 查看: 265

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

来源：力扣 No.200

思路：

1、遍历二维网格，计算遇到‘1’的次数，即为最终结果；

2、当遇到二维网格的值为‘1’时，进行广度优先搜索BFS，将遇到的'1'变为'0'；

3、继续遍历二维网格，遇到‘0’时continue。

坑：

二维网络里的值不是int类型的而是char类型的字符

优化空间：

BFS循环中，往里面添加坐标时，会有重复判断的情况

代码：

class Solution { private static int m; private static int n; public int numIslands(char[][] grid) { m = grid.length; n = grid[0].length; int res = 0; for(int x = 0; x < m; x++){ for(int y = 0; y < n; y++){ if(grid[x][y] == '0'){ continue; } res++; bfs(grid, x, y); } } return res; } public void bfs(char[][] grid, int cur_x, int cur_y){ Stack pos = new Stack(); pos.push(new int[]{cur_x, cur_y}); while(!pos.isEmpty()){ int[] curPos = pos.pop(); int curPos_x = curPos[0]; int curPos_y = curPos[1]; if(curPos_x >= m || curPos_y >= n || grid[curPos_x][curPos_y] == '0'){ continue; } // System.out.println(curPos_x+" "+curPos_y+" "+grid[curPos_x][curPos_y] + " " +pos.size()); grid[curPos_x][curPos_y] = '0'; pos.push(new int[]{curPos_x+1, curPos_y}); pos.push(new int[]{curPos_x, curPos_y+1}); if(curPos_y - 1 >= 0){ pos.push(new int[]{curPos_x, curPos_y-1}); }if(curPos_x - 1 >= 0){ pos.push(new int[]{curPos_x-1, curPos_y}); } } } }

【本文地址】

算法练习4

算法练习4

今日新闻

推荐新闻